686. 重复叠加字符串匹配

Solution Tips

问题的关键在于, 重复的必要次数是多少?

首先, 可以明确的是, 一定要重复到主串的长度大于子串, 才有可能匹配上. 重复次数记为 r1

然后, 假如子串一定可以匹配上, 那么子串的第一个字符一定是在未重复的主串中存在的. 如果不存在就不可能匹配上.

那么如果存在, 可以子串可以完整匹配到的起始位置也一定是在非重复的主串中的, 所以最多也只需要重复 r1 + 1 次

确定了重复的次数之后, 剩下的任务就是 kmp 匹配子串了

是否有必要使用 kmp 呢? 因为可以确定子串匹配的起始位置是有限的, 直接截取和子串长度相同的判断一下其实就 ok 了 ?